//------------------------------------------------------------------------------
// SortableArray.h
//------------------------------------------------------------------------------
// File provided for Microsoft Shared Source.
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF 
// ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO 
// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A 
// PARTICULAR PURPOSE.
//------------------------------------------------------------------------------
//
// CAtlArray with sorting/searching capabilities
//
//------------------------------------------------------------------------------

#pragma once

template<typename E, class ETraits = CElementTraits<E>>
class CSortableArray : public CAtlArray<E, ETraits>
{
public:
    size_t Search(INARGTYPE element, BOOL fReturnInsertionPoint, BOOL &fFound, LPARAM lParam);
    size_t InsertSorted(INARGTYPE element);
};

template<typename E, class ETraits>
size_t CSortableArray<E, ETraits>::Search(INARGTYPE element, BOOL fReturnInsertionPoint, BOOL &fFound, LPARAM lParam)
{
    ATLASSERT_VALID(this);

    fFound = FALSE;

    size_t cElt = GetCount();

    // Search the array using binary search.  If several adjacent
    // elements match the target element, the index of the first
    // matching element is returned.

    size_t iRet = -1; // assume no match
    int nCmp = 0;
    size_t iLow = 0;
    size_t iMid = 0;
    size_t iHigh = cElt - 1;

    while (iLow <= iHigh && iHigh < cElt)
    {
        iMid = (iLow + iHigh) / 2;

        nCmp = ETraits::CompareElementsOrderedParam(element, GetAt(iMid), lParam);

        if (0 > nCmp)
        {
            iHigh = iMid - 1; // First is smaller
        }
        else if (0 < nCmp)
        {
            iLow = iMid + 1; // First is larger
        }
        else
        {
            // Match; search back for first match
            fFound = TRUE;
            while (0 < iMid)
            {
                if (0 != ETraits::CompareElementsOrderedParam(element, GetAt(iMid-1), lParam))
                {
                    break;
                }
                else
                {
                    iMid--;
                }
            }
            break;
        }
    }

    if (fFound)
    {
        ATLASSERT(0 <= iMid);
        iRet = iMid;
    }
    else if (fReturnInsertionPoint)
    {
        // Did the search fail AND the insertion point is requested
        iRet = (0 < nCmp) ? iLow : iMid;
    }
    return iRet;
}

template<typename E, class ETraits>
size_t CSortableArray<E, ETraits>::InsertSorted(INARGTYPE element)
{
    BOOL fFound;
    size_t iIndex = Search(element, TRUE, fFound);
    if (iIndex != -1)
    {
        InsertAt(iIndex, element);
    }
    return size_t;
}

